// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-04-14 17:28
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DigitalDP;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 度的数量
 */
public class degreeNum {
    // 整数2^31,最小进制为二进制，所以数位设定为35防止出现数位溢出
    private final int N = 35;
    public int K, B;
    // 数位状态数组
    public int[][] f = new int[N][N];

    public degreeNum(int k, int b) {
        this.K = k;
        B = b;
    }

    // 状态数组初始化
    void init() {
        /*
            状态数组的定义是从i个数位中选取j个数位
         */
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    // 数位为0的情况状态为一
                    f[i][j] = 1;
                } else {
                    // 根据组合公式实现状态转移
                    f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
                }
            }
        }
    }

    // 状态转移方法
    public int dp(int n) {
        // 特值判断
        if (n == 0) {
            // 当传入的数字为0的时候，表示当前没有可以实现组合的个数
            return 0;
        }
        // nums列表用于存储传入数字的每一个位数的数
        List<Integer> nums = new ArrayList<>();
        while (n > 0) {
            nums.add(n % B);
            n /= B;
        }
        // 一个作为结果，一个作为前一个状态
        int res = 0, last = 0;
        // 从传入数字的第一位开始遍历
        for (int i = nums.size() - 1; i >= 0; i--) {
            int x = nums.get(i);
            // 只有当第一位数字大于0的时候才可以进行排列组合，否则就是到达最后一位
            // 对x进行分类讨论，x恰好为1的情况和x不为1的情况
            if (x > 0) {
                // x>=1,直接添加答案
                res += f[i][K - last];
                if (x > 1) {
                    // 因为这边记录的是左分支，如果当前位x填1，只要当前位大于1才能填入an-1 = 1的情况
                    if (K - last - 1 >= 0) {
                        res += f[i][K - last - 1];
                        // 这里可以直接break的原因是当an-1 > 1的时候，an-1肯定不是1，即右节点不合法
                        break;
                    }
                } else {
                    // 右分支节点信息，右分支节点的节点值恰好为1
                    last++;
                    if (last > K) {
                        break;
                    }
                }
            }
            // 最右分支方案
            if (i == 0 && last == K) {
                res++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        degreeNum dn = new degreeNum(8, 2);
        dn.init();
        int l, r;
        Scanner myScanner = new Scanner(System.in);
        l = myScanner.nextInt();
        r = myScanner.nextInt();
        System.out.println(dn.dp(r) - dn.dp(l - 1));
    }

}
